//给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串，
// 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
//
// 
//
// 示例 1： 
//
// 
//输入：s = "aaabb", k = 3
//输出：3
//解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
// 
//
// 示例 2： 
//
// 
//输入：s = "ababbc ",
//输出：5k = 2
//解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 10⁴ 
// s 仅由小写英文字母组成 
// 1 <= k <= 10⁵ 
// 
// Related Topics 哈希表 字符串 分治 滑动窗口 👍 553 👎 0


import java.util.HashSet;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestSubstring(String s, int k) {
         int n = s.length();
         return dfs(s, 0, n-1, k);
    }

    public int dfs(String s, int left, int right, int k){
        int alpha[] = new int[26];
        for (int i = left; i <= right; i++){
            alpha[s.charAt(i) - 'a']++;
        }

        //找到第一个出现次数小于k的字母
        char split = 0;
        for (int i = 0; i < 26; i++){
            if(alpha[i] > 0 && alpha[i] < k){
                split = (char) alpha[i+97];
                break;
            }
        }

        if(split == 0){
            return right - left + 1;
        }
        int i = left;
        int ret = 0;
        while (i <= right){
        while (i <= right && s.charAt(i) == split){
            i++;
        }

        if(i > right){
            break;
        }
        left = i;
        while (i <= right && s.charAt(i) != split){
            i++;
        }
        int length = dfs(s, left, i-1, k);
        ret = Math.max(ret, length) ;
        }
        return ret;
    }








//    public int dfs1(String s, int l, int r, int k){
//       int alpha[] = new int[26];
//       //统计s中各中字母的次数
//       for (int i = l; i <=r; i++){
//           alpha[s.charAt(i) - 'a']++;
//       }
//        //用于保存在当前字符串中出现次数少于k的第一个元素
//       char split = 0;
//       for(int i = 0; i < 26; i++){
//           if(alpha[i] > 0 && alpha[i] < k) {
//               split = (char) (i + 'a');
//               break;
//           }
//       }
//       //如果不存在出现次数小于k的元素，则整个字符串都满足条件
//       if(split == 0){
//           return r - l + 1;
//       }
//
//       int i = l;
//       int ret = 0;
//       while (i <= r){
//           while (i <= r && s.charAt(i) == split){
//               i++;
//           }
//           //如果i走到r后面，跳出循环。
//           if(i > r){
//              break;
//           }
//           int start = i;
//           //找到split的前一个元素
//           while (i <= r && s.charAt(i) != split){
//               i++;
//           }
//            //最长子串的长度在start 和i -1之间
//           int length = dfs1(s, start, i-1, k);
//           ret = Math.max(length, ret);
//       }
//        return ret;
//    }
}
//leetcode submit region end(Prohibit modification and deletion)
